package leetcode103

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func zigzagLevelOrder(root *TreeNode) [][]int {
	res := make([][]int, 0)
	if root == nil {
		return res
	}
	nowLevelNode := []*TreeNode{root}
	revFlag := false
	for {
		nexLevelNode := make([]*TreeNode, 0)
		currentLevelValue := make([]int, len(nowLevelNode))
		for i, node := range nowLevelNode {
			if revFlag {
				currentLevelValue[len(nowLevelNode)-i-1] = node.Val
			} else {
				currentLevelValue[i] = node.Val
			}
			if node.Left != nil {
				nexLevelNode = append(nexLevelNode, node.Left)
			}
			if node.Right != nil {
				nexLevelNode = append(nexLevelNode, node.Right)
			}
		}
		res = append(res, currentLevelValue)
		nowLevelNode = nexLevelNode
		revFlag = !revFlag
		if len(nexLevelNode) == 0 {
			break
		}
	}
	return res
}
